JoyOI 数字三角形2 题解

发表于 | 分类于 | | 热度: ℃

Description

给定数字三角形，要求最后答案 $mod$ $100$ 最大。

数据范围：$n<=25$

Solution

设 $bool$ $f[i][j][k]$ 为走到 $(i,j)$ 这个点 $mod$ $100$ 能不能得到 $k$。更新使用刷表法。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int n, f[100][100][150], a[50][50];
int main()
{
    memset(f, 0, sizeof(f));
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= i; j++)
            scanf("%d", &a[i][j]);
    f[1][1][a[1][1] % 100] = 1;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= i; j++)
            for(int k = 0; k < 100; k++)
                if(f[i][j][k])
                {
                    f[i + 1][j][(k + a[i + 1][j]) % 100] = 1;
                    f[i + 1][j + 1][(k + a[i + 1][j + 1]) % 100] = 1;
                }
    int ans = -0x3f3f3f3f;
    for(int i = 1; i <= n; i++)
        for(int k = 0; k < 100; k++)
            if(f[n][i][k]) ans = max(ans, k);
    printf("%d", ans);
    return 0;
}